This study seeks to evaluate the effect of heterologous exposure to different viruses as vectors for prostate cancer vaccination. A recombinant vaccinia virus and fowlpox virus expressing the prostate-specific antigen (PSA) have been constructed and tested in a phase I clinical trial previously. This study will randomize patients with D0 prostate cancer to one of three arms to evaluate the effects of boosting with alternate vectors on PSA progression, clinical response, and PSA-specific T-cell reactivity. The first group of patients will receive four injections of fowlpox-PSA every six weeks. A second group will receive a single vaccinia-PSA vaccine followed by three fowlpox-PSA injections every six weeks. The third group will receive three fowlpox-PSA vaccines followed by a single vaccinia-PSA vaccine. The patients will be followed for clinical and laboratory toxicity every six weeks and immune responses will be assessed every 12 weeks. The trial seeks to enroll 60 patients and is a multi-institutional trial. We expect an accrual of 10 patients at Albert Einstein and have now enrolled 4 patients to date. This has resulted in 8 GCRC visits.